package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/fc897457408f4bbe9d3f87588f497729?tpId=188&&tqId=38571&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC111 最大数</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个nums数组由一些非负整数组成，现需要将他们进行排列并拼接，每个数不可拆分，使得最后的结果最大，返回值需要是string类型，否则可能会溢出
 * <p>
 * 提示:
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 10000
 * <p>
 * 示例1
 * 输入：
 * [30,1]
 * <p>
 * 返回值：
 * "301"
 * <p>
 * 示例2
 * 输入：
 * [2,20,23,4,8]
 * <p>
 * 返回值：
 * "8423220"
 * <p>
 * 示例3
 * 输入：
 * [2]
 * <p>
 * 返回值：
 * "2"
 * <p>
 * 示例4
 * 输入：
 * [10]
 * <p>
 * 返回值：
 * "10"
 * <p>
 * 备注：
 * 输出结果可能非常大，所以你需要返回一个字符串而不是整数。
 *
 * @author or2
 * @date 2021年09月26日 时间: 11:26
 */
public class NC111 {
    private static StringBuilder STRING_BUILDER = new StringBuilder();

    /**
     * 最大数
     *
     * @param nums int整型一维数组
     * @return string字符串
     */
    public String solve(int[] nums) {
        /*数组排序*/
        quickSortCustom(nums, 0, nums.length);
        /*整理答案*/
        StringBuilder builder = new StringBuilder();
        for (int num : nums)
            builder.append(num);
        /*特殊答案判断*/
        String ans;
        if (nums[0] == 0)
            ans = "0";
        else
            ans = builder.toString();
        /*帮助gc*/
        nums = null;
        builder = null;
        STRING_BUILDER = null;
        System.gc();
        return ans;
    }

    /**
     * 对 arr 数组的 [start, end) 区间进行快速排序
     *
     * @param arr   被排序的数组
     * @param start 开始排序的下标
     * @param end   终止的下标(不包含该下标)
     */
    public void quickSort(int[] arr, int start, int end) {
        /*随机选定标定点*/
        int beacon = arr[start + (int) ((end - start) * Math.random())];

        /*划分*/
        int lt = start, gt = end, eq = lt;
        while (eq < gt) {
            if (arr[eq] == beacon) eq++;
            else if (arr[eq] < beacon) swap(arr, lt++, eq++);
            else swap(arr, eq, --gt);
        }

        /*解决子问题*/
        if (start < lt - 1)
            quickSort(arr, start, lt);
        if (gt < end - 1)
            quickSort(arr, gt, end);
    }

    private void swap(int[] arr, int lt, int gt) {
        int swap = arr[lt];
        arr[lt] = arr[gt];
        arr[gt] = swap;
    }

    /**
     * 对 arr 数组的 [start, end) 区间进行快速排序
     *
     * @param arr   被排序的数组
     * @param start 开始排序的下标
     * @param end   终止的下标(不包含该下标)
     */
    public void quickSortCustom(int[] arr, int start, int end) {
        /*随机选定标定点*/
        int beacon = arr[start + (int) ((end - start) * Math.random())];

        /*划分*/
        int lt = start, gt = end, eq = lt;
        while (eq < gt) {
            int compare = compare(arr[eq], beacon);
            if (compare == 0) eq++;
            else if (compare < 0) swap(arr, lt++, eq++);
            else swap(arr, eq, --gt);
        }

        /*解决子问题*/
        if (start < lt - 1)
            quickSortCustom(arr, start, lt);
        if (gt < end - 1)
            quickSortCustom(arr, gt, end);
    }

    /**
     * 该题 大小比较器
     *
     * @param x 数值一
     * @param y 数值二
     * @return 基于字符串拼接的大小比较
     */
    private int compare(int x, int y) {
        STRING_BUILDER.delete(0, STRING_BUILDER.length());
        String str1 = STRING_BUILDER.append(x).append(y).toString();
        STRING_BUILDER.delete(0, STRING_BUILDER.length());
        String str2 = STRING_BUILDER.append(y).append(x).toString();
        return -str1.compareTo(str2);
    }
}

